package solution.design;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @author zhangmin
 * @create 2021-09-28 21:06
 *
 * LFU缓存，最不经常使用缓存算法-----HashMap<Integer, LinkedHashSet<Integer>>
 */
public class LFUCache {

    //容量
    int capacity;
    //最小频次
    int minFreq;
    //key到val映射
    HashMap<Integer,Integer> kToV;
    //key到freq映射
    HashMap<Integer,Integer> kToF;
    //freq到key的列表映射，列表是有时序性的
    HashMap<Integer, LinkedHashSet<Integer>> fToKs;

    public LFUCache(int capacity) {
        this.capacity=capacity;
        this.minFreq=0;
        kToV=new HashMap<>();
        kToF=new HashMap<>();
        fToKs=new HashMap<>();
    }
    //删除最小的频率的key
    private void removeMinFreqKey() {
        //通过minF来获得最小key的列表
        LinkedHashSet<Integer> keyList=fToKs.get(this.minFreq);
        //最先被插入的那个key就是该被淘汰的
        int deletekey=keyList.iterator().next();
        //更新kToF
        keyList.remove(deletekey);
        if (keyList.isEmpty()){
            fToKs.remove(this.minFreq);
        }
        kToV.remove(deletekey);
        kToF.remove(deletekey);
    }

    //get后需要增加频率
    private void increaseFreq(int key) {
        int freq=kToF.get(key);
        //更新KF
        kToF.put(key,freq+1);
        //更新FK,将 key 从 freq 对应的列表中删除,将 key 加入 freq + 1 对应的列表中
        fToKs.get(freq).remove(key);
        fToKs.putIfAbsent(freq+1,new LinkedHashSet<>());
        fToKs.get(freq+1).add(key);
        //如果 freq 对应的列表空了，移除这个 freq
        if (fToKs.get(freq).isEmpty()){
            fToKs.remove(freq);
            if (freq==this.minFreq){
                // 如果这个 freq 恰好是 minFreq，更新 minFreq
                this.minFreq++;
            }
        }
    }
    public int get(int key) {
        if (!kToV.containsKey(key)){
            return -1;
        }
        // 增加 key 对应的 freq
        increaseFreq(key);
        return kToV.get(key);
    }

    public void put(int key, int value) {
        if (this.capacity <= 0) return;
        /* 若 key 已存在，修改对应的 val 即可 */
        if (kToV.containsKey(key)){
            kToV.put(key,value);
            increaseFreq(key);
            return;
        }
        /* key 不存在，需要插入 */
        /* 容量已满的话需要淘汰一个 freq 最小的 key */
        if (this.capacity<=kToV.size()){
            removeMinFreqKey();
        }
        /* 插入 key 和 val，对应的 freq 为 1 */
        // 插入 KV 表
        kToV.put(key,value);
        // 插入 KF 表
        kToF.put(key,1);
        // 插入 FK 表
        fToKs.putIfAbsent(1,new LinkedHashSet<>());
        fToKs.get(1).add(key);
        // 插入新 key 后最小的 freq 肯定是 1
        this.minFreq=1;
    }
}
